# 此文件仅用于实现归并排序中的合并两个有序序列片段的函数
def Merge(nums: list, left, mid, right):
    i = left
    j = mid + 1
    temp = []
    while i <= mid and j <= right:
        if nums[i - 1] < nums[j - 1]:
            temp.append(nums[i - 1])
            i += 1
        else:
            temp.append(nums[j - 1])
            j += 1
    if i <= mid:
        temp.extend(nums[i - 1 : mid])

    if j <= right:
        temp.extend(nums[j - 1 : right])
    nums[left - 1 : right] = temp
    return nums


if __name__ == "__main__":
    nums = [10, 30, 50, 70, 90, 20, 40, 60, 80]
    nums = Merge(nums, 1, 5, 9)
    print(nums)
